package Alibaba;

import common.ListNode;

import java.util.*;

/**
 * @author zhangmin
 * @create 2022-01-20 10:14
 *
 * 127. 单词接龙
 * 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
 * 序列中第一个单词是 beginWord 。序列中最后一个单词是 endWord 。每次转换只能改变一个字母。
 * 转换过程中的中间单词必须是字典 wordList 中的单词。给你两个单词 beginWord 和 endWord 和一个字典 wordList ，
 * 找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
 * 1、回溯：路径：已选择的从begin开始的变化过程
 *         选择：wordlist中与当前单词只有一个不同的列表
 *         终止条件：到达endword或world中所有单词都已访问过
 *   ---超时
 * 2、广度优先搜索
 */
public class ladderLength127 {

    LinkedList<LinkedList<String>> res;
    boolean[] visited;
    List<String> worldlist;
    void getPath(String cur, String endWord, LinkedList<String> path){
        if (cur.equals(endWord)){
            res.add(new LinkedList<>(path));
            return;
        }
        //作出选择
        for (int i = 0; i < worldlist.size(); i++) {
            String s = worldlist.get(i);
            if (!visited[i]&&isOnedif(cur,s)){
                visited[i]=true;
                path.add(cur);
                getPath(s,endWord,path);
                path.removeLast();
                visited[i]=false;
            }
        }
    }
    boolean isOnedif(String s1,String s2){
        boolean falg=false;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i)!=s2.charAt(i)){
                if (falg){
                    return false;
                }else {
                    falg=true;
                }
            }
        }
        return falg;
    }
    public int ladderLength1(String beginWord, String endWord, List<String> wordList) {
        res=new LinkedList<>();
        visited=new boolean[wordList.size()];
        worldlist=wordList;
        getPath(beginWord,endWord,new LinkedList<>());
        int len=Integer.MAX_VALUE;
        for (LinkedList<String> list:res) {
            System.out.println(list);
            len=Math.min(len,list.size()+1);
        }
        return len==Integer.MAX_VALUE?0:len;
    }

    //2、广度优先
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //用set记录wordlist的元素
        Set<String> set=new HashSet<>(wordList);
        if(set.size()==0||!set.contains(endWord)){
            return 0;
        }
        set.remove(beginWord);
        //广度优先搜索：
        Queue<String> queue=new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited=new HashSet<>();
        visited.add(beginWord);
        //开始搜索，将与队列中当前节点可以直接到的节点加入到队列尾部
        int res=1;
        while (!queue.isEmpty()){
            int num = queue.size();
            for (int i = 0; i < num; i++) {
                String cur = queue.poll();
                if (isOnedif(cur,endWord)){
                    return res+1;
                }
                for (String word:wordList) {
                    if (!visited.contains(word)&&isOnedif(cur,word)){
                        queue.offer(word);
                        visited.add(word);
                    }
                }
            }
            res++;
        }
        return 0;
    }

    public static void main(String[] args) {
        String beginWord = "hit", endWord = "cog";
        List<String> wordList = new LinkedList<>();
        wordList.add("hot");
        wordList.add("dot");
        wordList.add("dog");
        wordList.add("lot");
        wordList.add("log");
        wordList.add("cog");
        ladderLength127 obj=new ladderLength127();
        System.out.println(obj.ladderLength(beginWord,endWord,wordList));
    }
}
